package com.shixianjun;
/**
 * 有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组nums中。
 *
 * 现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。这里的 i - 1 和 i + 1 代表和i相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。
 *
 * 求所能获得硬币的最大数量。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/burst-balloons
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class 戳气球 {

    public static void main(String[] args) {
        int[] nums =  new int[]{2,3,48,7,99,1,3,77};
        int result = maxCoins(nums);
        System.out.print("result : " + result + "\n");
    }

    public static int maxCoins(int[] nums) {
        // 在两侧增加 1 的元素
        int n = nums.length;
        int[] help = new int[n + 2];
        help[0] = 1;
        help[n + 1] = 1;
        for (int i = 1; i <= n; i++) {
            help[i] = nums[i - 1];
        }

        // 动态规划
        int[][] dp = new int[n + 1][n + 1];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                dp[i][j] = -1;
            }
        }
        return progress(help, 1, n, dp);
    }

    /*
    *
    * */
    public static int progress(int[] nums, int L, int R, int[][] dp) {

        if (dp[L][R] != -1) {
            return dp[L][R];
        }
        // L == R 说明是第一个被戳的
        if (L == R) {
            return nums[L - 1] * nums[L] * nums[L + 1];
        }

        int ans;
        // 最后戳破L位置气球的得分
        int pL = progress(nums, L + 1, R, dp) + nums[L - 1] * nums[L] * nums[R + 1];
        // 最后戳破R位置气球的得分
        int pR = progress(nums, L, R - 1, dp) + nums[R + 1] * nums[R] * nums[L - 1];
        ans = Math.max(pL, pR);

        // 尝试中间位置最后戳破的得分
        for (int mid = L + 1; mid < R; mid++) {
            int pM = progress(nums, L, mid - 1, dp) + nums[L - 1] * nums[mid] * nums[R + 1] + progress(nums, mid + 1, R, dp);
            ans = Math.max(ans, pM);
        }
        dp[L][R] = ans;
        return ans;
    }
}
